P2303 [SDOI2012] Longge 的问题

i=1n(i,n)\sum_{i=1}^n(i,n)

dndi=1n[(i,n)=d]\sum_{d|n}d\sum_{i=1}^n[(i,n)=d]

dndid=1n[(id,n)=1]\sum_{d|n}d\sum_{id=1}^{n}[(id,n)=1]

dndφ(nd)\sum_{d|n} d\varphi(\frac{n}{d})

然后枚举因数暴力计算.

#include <cstdio>
#define LL long long

const int MAXN = 1 << 17;
LL n;

int prn , prime[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) prime[ ++ prn ] = i;
		for( int j = 1 ; j <= prn && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
		}
	}
}
LL phi( LL n ) {
	LL Ans = n;
	for( int i = 1 ; i <= prn ; i ++ ) {
		if( n < prime[ i ] ) break;
		if( n % prime[ i ] == 0 ) {
			while( n % prime[ i ] == 0 ) n /= prime[ i ];
			Ans = Ans / prime[ i ] * ( prime[ i ] - 1 );
		}
	}
	if( n > 1 ) Ans = Ans / n * ( n - 1 );
	return Ans;
}
LL f( LL n ) {
	LL Ans = 0;
	for( LL i = 1 ; i * i <= n ; i ++ )
		if( n % i == 0 ) Ans += i * phi( n / i ) + ( i * i == n ? 0 : phi( i ) * ( n / i ) );
	return Ans;
}

int main( ) {
	sieve( );
	scanf("%lld",&n);
	printf("%lld\n", f( n ) );
	return 0;
}